17. 电话号码的字母组合
17. 电话号码的字母组合
分析
77. 组合 是从同一个集合 m 中取 n 个元素进行组合，m<n，且组合不能重复，而这道题是从 m 个不同的集合中取 m 个元素进行组合，每个集合取出来一个元素，不用考虑组合重复的问题，更简单。
方法是，循环来源字符串的每一个位置上的数字对应的所有可能即可，方法是用 for 循环嵌套，每一层 for 循环遍历的都是这个位置上的所有可能的情况。
我们直接用字符串数组来保存数字跟字符的映射关系，数字为索引，字符串为数字对应的所有字符的集合。
现在我们来讲一遍思路∶我们从来源字符串的第一个字符开始，index 为 0，在字符串数组中获取数字对应的字符串，for 遍历这个字符串中的所有字符，同时在 for 循环中进行递归调用，传入 index+1，表示处理来源字符串的下一个字符。
这里跟 77. 组合 有一个区别就是，因为我们遍历的是多个不同的集合，所以我们进行递归调用的时候，传入的是 index+1，而不是当前 for 循环的循环变量 i。
这里有两个优化的点：
- 获取字符串的每一个字符之后，因为我们知道这个字符对应的数字是 1-9，所以可以直接用这个字符减去 '0' 来计算这个字符对应的 int 类型的额数字，原理是，每一个字符都有一个 ASCII码，比如 '0' 的码就是 48，'1' 的码是 49，以此类推，当我们用减号处理两个 char 字符的时候，char 字符会自动转化为对应的 ASCII 码进行计算，因此，我们通过计算字符与 '0' 的距离就可以计算出这个字符对应的数字，这个比
Integer.valueOf(""+charObj);要快非常多。 我们在 76. 最小覆盖子串 中也学习过 char 到 ASCII 码的转化。 - 不要使用 String，尽量使用
StringBuilder，注意，不能无脑用 String 字符串拼接，性能会慢好几倍，因此能用 StringBuilder 的地方一定要用 StringBuilder。我们在 257. 二叉树的所有路径 中也遇到过这个小优化性能有问题。
解题
class Solution {
public String[] numMap = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> result = new ArrayList<>();
public List<String> letterCombinations(String digits) {
backTraceing(digits,0,new StringBuilder());
return result;
}
public void backTraceing(String digits,int index,StringBuilder sb){
if(index >= digits.length()){
result.add(sb.toString());
return;
}
char ele = digits.charAt(index);
// 直接通过减去 '0' 这个字符，实际上是减去 '0' 的 ASCII 码来快速确定 int 值
int eleInt = ele -'0';
// 不能大于9，也不能小于0
if(eleInt<0 || eleInt>9){
return;
}
char[] arr = numMap[eleInt].toCharArray();
for(int i=0;i<arr.length;i++){
int length = sb.length();
sb.append(arr[i]);
backTraceing(digits,index+1,sb);
sb.setLength(length);
}
}
}